배열 (Array)
배열은 연속된 메모리 공간에 저장된 동일한 타입의 데이터 집합이다. 인덱스를 통해 O(1) 시간에 접근할 수 있지만, 삽입/삭제 시 O(n) 시간이 걸린다.
특징
- 접근: O(1) - 인덱스로 직접 접근
- 검색: O(n) - 선형 검색 필요
- 삽입: O(n) - 요소 이동 필요
- 삭제: O(n) - 요소 이동 필요
Python 예제
# Python 리스트는 동적 배열로 구현됨
arr = [1, 2, 3, 4, 5]
# 접근: O(1)
print(arr[0]) # 1
# 삽입: O(n)
arr.insert(2, 10) # [1, 2, 10, 3, 4, 5]
# 삭제: O(n)
arr.remove(10) # [1, 2, 3, 4, 5]
# 검색: O(n)
index = arr.index(3) # 2
링크드리스트 (Linked List)
링크드리스트는 노드들이 포인터로 연결된 자료구조이다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함한다. 삽입/삭제는 O(1)이지만 접근은 O(n)이다.
특징
- 접근: O(n) - 순차 탐색 필요
- 검색: O(n) - 순차 탐색 필요
- 삽입: O(1) - 포인터만 변경
- 삭제: O(1) - 포인터만 변경
Python 예제
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def delete(self, data):
if not self.head:
return
if self.head.data == data:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.data == data:
current.next = current.next.next
return
current = current.next
def display(self):
elements = []
current = self.head
while current:
elements.append(current.data)
current = current.next
return elements
# 사용 예제
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
print(ll.display()) # [0, 1, 2, 3]
ll.delete(2)
print(ll.display()) # [0, 1, 3]
스택 (Stack)
스택은 LIFO(Last In First Out) 원칙을 따르는 자료구조이다. 한쪽 끝에서만 삽입과 삭제가 이루어진다.
특징
- push: O(1) - 맨 위에 추가
- pop: O(1) - 맨 위에서 제거
- peek: O(1) - 맨 위 요소 확인
Python 예제
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
return None
return self.items.pop()
def peek(self):
if self.is_empty():
return None
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# 사용 예제
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek()) # 3
print(stack.pop()) # 3
print(stack.pop()) # 2
큐 (Queue)
큐는 FIFO(First In First Out) 원칙을 따르는 자료구조이다. 한쪽 끝에서 삽입, 다른 쪽 끝에서 삭제가 이루어진다.
특징
- enqueue: O(1) - 뒤에 추가
- dequeue: O(1) - 앞에서 제거
- front: O(1) - 앞 요소 확인
Python 예제
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.is_empty():
return None
return self.items.pop(0)
def front(self):
if self.is_empty():
return None
return self.items[0]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# 사용 예제
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.front()) # 1
print(queue.dequeue()) # 1
print(queue.dequeue()) # 2
트리 (Tree)
트리는 노드들이 계층 구조로 연결된 자료구조이다. 루트 노드에서 시작하여 각 노드는 여러 자식 노드를 가질 수 있다.
이진 트리 (Binary Tree)
각 노드가 최대 2개의 자식을 가지는 트리이다.
특징
- 검색: O(log n) - 균형 트리인 경우
- 삽입: O(log n) - 균형 트리인 경우
- 삭제: O(log n) - 균형 트리인 경우
Python 예제
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, data):
if not self.root:
self.root = TreeNode(data)
else:
self._insert(self.root, data)
def _insert(self, node, data):
if data < node.data:
if node.left is None:
node.left = TreeNode(data)
else:
self._insert(node.left, data)
else:
if node.right is None:
node.right = TreeNode(data)
else:
self._insert(node.right, data)
def inorder(self, node):
if node:
self.inorder(node.left)
print(node.data, end=' ')
self.inorder(node.right)
def preorder(self, node):
if node:
print(node.data, end=' ')
self.preorder(node.left)
self.preorder(node.right)
def postorder(self, node):
if node:
self.postorder(node.left)
self.postorder(node.right)
print(node.data, end=' ')
# 사용 예제
tree = BinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(2)
tree.insert(4)
tree.insert(6)
tree.insert(8)
print("Inorder:", end=' ')
tree.inorder(tree.root) # 2 3 4 5 6 7 8
print("\nPreorder:", end=' ')
tree.preorder(tree.root) # 5 3 2 4 7 6 8
print("\nPostorder:", end=' ')
tree.postorder(tree.root) # 2 4 3 6 8 7 5
힙 (Heap)
힙은 완전 이진 트리 기반의 우선순위 큐 자료구조이다. 최소 힙은 부모가 자식보다 작고, 최대 힙은 부모가 자식보다 크다.
특징
- 삽입: O(log n)
- 삭제: O(log n)
- 최소/최대값 접근: O(1)
Python 예제
import heapq
# Python의 heapq 모듈은 최소 힙을 제공
heap = []
# 삽입: O(log n)
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
print(heap) # [1, 3, 7, 5] - 최소값이 맨 앞
# 최소값 제거: O(log n)
min_val = heapq.heappop(heap)
print(min_val) # 1
print(heap) # [3, 5, 7]
# 최소값 확인: O(1)
print(heap[0]) # 3
# 최대 힙 구현 (음수 사용)
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -7)
max_val = -heapq.heappop(max_heap)
print(max_val) # 7
해시 (Hash)
해시 테이블은 키-값 쌍을 저장하는 자료구조이다. 해시 함수를 사용하여 키를 인덱스로 변환하여 O(1) 평균 시간에 접근할 수 있다.
특징
- 삽입: O(1) 평균, O(n) 최악
- 검색: O(1) 평균, O(n) 최악
- 삭제: O(1) 평균, O(n) 최악
Python 예제
# Python의 dict는 해시 테이블로 구현됨
hash_map = {}
# 삽입: O(1)
hash_map['apple'] = 5
hash_map['banana'] = 3
hash_map['cherry'] = 8
# 검색: O(1)
print(hash_map['apple']) # 5
print(hash_map.get('banana')) # 3
print(hash_map.get('grape', 0)) # 0 (키가 없으면 기본값 반환)
# 삭제: O(1)
del hash_map['cherry']
print(hash_map) # {'apple': 5, 'banana': 3}
# 해시 충돌 처리 예제 (체이닝 방식)
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash(key)
for pair in self.table[index]:
if pair[0] == key:
pair[1] = value
return
self.table[index].append([key, value])
def get(self, key):
index = self._hash(key)
for pair in self.table[index]:
if pair[0] == key:
return pair[1]
return None
def delete(self, key):
index = self._hash(key)
for i, pair in enumerate(self.table[index]):
if pair[0] == key:
del self.table[index][i]
return
# 사용 예제
ht = HashTable()
ht.insert('apple', 5)
ht.insert('banana', 3)
print(ht.get('apple')) # 5
ht.delete('banana')
print(ht.get('banana')) # None
그래프 (Graph)
그래프는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조이다. 정점들 간의 관계를 표현하는 조직도로 그래프는 정점마다 간선이 없을수도 있고 있을수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는 부분에서 트리와 다르다.
- 정점(Vertex): 노드(node)라고도 하며, 정점에는 데이터가 저장된다.
- 간선(Edge): 노드간의 관계를 나타낸다.
특징
- 인접 리스트: 공간 O(V + E), 간선 확인 O(degree)
- 인접 행렬: 공간 O(V²), 간선 확인 O(1)
Python 예제
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
# 무방향 그래프인 경우
self.graph[v].append(u)
def dfs(self, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in self.graph[start]:
if neighbor not in visited:
self.dfs(neighbor, visited)
def bfs(self, start):
visited = set()
queue = [start]
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex, end=' ')
for neighbor in self.graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 사용 예제
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
print("DFS:", end=' ')
g.dfs(0) # 0 1 2 3 4
print("\nBFS:", end=' ')
g.bfs(0) # 0 1 2 3 4
자료구조 비교
| 자료구조 | 접근 | 검색 | 삽입 | 삭제 | 공간 복잡도 |
|---|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(n) | O(n) |
| 링크드리스트 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 큐 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 이진 트리 | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| 힙 | O(1)* | O(n) | O(log n) | O(log n) | O(n) |
| 해시 테이블 | O(1)* | O(1)* | O(1)* | O(1)* | O(n) |
| 그래프 | O(V+E) | O(V+E) | O(1) | O(1) | O(V+E) |
*평균 시간 복잡도